#ifndef __BINARY_SEARCH_TREE__
#define __BINARY_SEARCH_TREE__


template <typename B>
struct BinarySearchTree {
    using BinaryTree = B;
    using Value = typename BinaryTree::Value;
    using Pointer = typename BinaryTree::Pointer;

    Pointer& root;

    BinarySearchTree(Pointer& root) : root(root) { }

    Pointer min() const;
    Pointer max() const; 
                          Pointer find(const Value& value) const { return find(value, comp); }
    template <typename F> Pointer find(const Value& value, F comp) const;

    Pointer& minRef() const;
    Pointer& maxRef() const;
                          Pointer& findRef(const Value& value) { return findRef(value, comp); }
    template <typename F> Pointer& findRef(const Value& value, F comp);

                          std::pair<Pointer, bool> insert(Value&& value) { return _insert(std::move(value), comp); }
                          std::pair<Pointer, bool> insert(const Value& value) { return _insert(value, comp); }
    template <typename F> std::pair<Pointer, bool> insert(Value&& value, F comp) { return _insert(std::move(value), comp); }
    template <typename F> std::pair<Pointer, bool> insert(const Value& value, F comp) { return _insert(value, comp); }

    bool remove(const Value& value) { return remove(value, comp); }
    template <typename F> bool remove(const Value& value, F comp);

    static int comp(const Pointer& node, const Value& value) { return node ? node->value - value : 0; }

private:
    template <typename V, typename F> std::pair<Pointer, bool> _insert(V&& value, F comp); 
};

template <typename B>
typename BinarySearchTree<B>::Pointer
BinarySearchTree<B>::min() const {
    if(auto node = root) {
        while(node->left)
            node = node->left;
        return node;
    }
    else
        return node;
}

template <typename B>
typename BinarySearchTree<B>::Pointer
BinarySearchTree<B>::max() const {
    if(auto node = root) {
        while(node->right)
            node = node->right;
        return node;
    }
    else
        return node;
}

template <typename B>
typename BinarySearchTree<B>::Pointer&
BinarySearchTree<B>::minRef() const {
    if(auto node = root) {
        decltype(node) nodeParent;

        while(node->left) {
            nodeParent = node;
            node = node->left;
        }

        return nodeParent ? nodeParent->left : root;
    }
    else
        return root;
}

template <typename B>
typename BinarySearchTree<B>::Pointer&
BinarySearchTree<B>::maxRef() const {
    if(auto node = root) {
        decltype(node) nodeParent;

        while(node->right) {
            nodeParent = node;
            node = node->right;
        }

        return nodeParent ? nodeParent->right : root;
    }
    else
        return root;
}

template <typename B>
template <typename F>
typename BinarySearchTree<B>::Pointer
BinarySearchTree<B>::find(const Value& value, F comp) const {
    auto node = root;
    while(node) {
        auto result = comp(node, value);
        if(result < 0)
            node = node->right;
        else if(result > 0)
            node = node->left;
        else
            break;
    }
    return node;
} 

template <typename B>
template <typename F>
typename BinarySearchTree<B>::Pointer&
BinarySearchTree<B>::findRef(const Value& value, F comp) {
    if(auto node = root) {
        if(node->value == value)
            return root;

        decltype(node) nodeParent = node;
        decltype(comp(node, value)) lastResult = 0;

        do {
            auto result = comp(node, value); 
            if(result < 0) {
                lastResult = result;
                nodeParent = node;
                node = node->right;
            }
            else if(result > 0) {
                lastResult = result;
                nodeParent = node;
                node = node->left;
            }
            else
                break;
        }
        while(node);

        return (lastResult < 0) ? 
            nodeParent->right :
            nodeParent->left;
    }
    else 
        return root; 
} 

template <typename B>
template <typename V, typename F>
std::pair<typename BinarySearchTree<B>::Pointer, bool> 
BinarySearchTree<B>::_insert(V&& value, F comp) {
    if(!root) {
        root.reset(new BinaryTree(std::forward<V>(value)));
        return std::make_pair(root, true);
    }
    else {
        auto node = root;
        auto lastNode = root;
        decltype(comp(node, value)) result;

        do {
            result = comp(node, value);

            if(result < 0) {
                lastNode = node;
                node = node->right;
            } 
            else if(result > 0) {
                lastNode = node;
                node = node->left;
            }
            else
                return std::make_pair(node, false);
        } while(node);

        if(result < 0)
            node = lastNode->right = Pointer(new BinaryTree(std::forward<V>(value)));
        else
            node = lastNode->left = Pointer(new BinaryTree(std::forward<V>(value)));

        return std::make_pair(node, true);
    }
}

template <typename B> 
template <typename F> 
bool BinarySearchTree<B>::remove(const Value& value, F comp) { 
    if(auto& result = findRef(value)) {
        if(result->left && result->right) {
            auto& maxNode = BinarySearchTree(result->left).maxRef();
            result->value = std::move(maxNode->value);
            maxNode = std::move(maxNode->left);
        }
        else if(result->left) {
            result = std::move(result->left);
        }
        else if(result->right) {
            result = std::move(result->right);
        }
        else if(result == root) {
            root.reset();
        } 
        return true;
    }
    else
        return false;
}

#endif
